package com.ma.graph;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution210BFS {

    public int[] findOrder(int numCourses, int[][] prerequisites) {

        List<Integer>[] graph = buildGraph(numCourses, prerequisites);
        //计算入度
        int[] indgree = new int[numCourses];
        for (int[] edge : prerequisites) {
            int from = edge[1];
            int to = edge[0];
            indgree[to]++;
        }
        //入度为0的节点进入队列
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indgree[i] == 0) {
                q.offer(i);
            }
        }
        int[] res = new int[numCourses];
        int count = 0;
        while (!q.isEmpty()) {
            int cur = q.poll();
            res[count] = cur;
            count++;
            for (int next : graph[cur]) {
                indgree[next]--;
                if (indgree[next] == 0) {
                    q.offer(next);
                }
            }
        }
        if(count!=numCourses){
            return new int[]{};
        }
        return res;
    }


    List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = new LinkedList[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new LinkedList<>();
        }
        for (int[] edge : prerequisites) {
            int from = edge[1];
            int to = edge[0];
            graph[from].add(to);
        }
        return graph;
    }

    public static void main(String[] args) {
        int numCourses = 4;
        int[][] prerequisites = {{1, 0}, {2, 0},{3,1},{3,2}};

        //输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
        //输出：[0,2,1,3]
        Solution210BFS solution = new Solution210BFS();
        int[] order = solution.findOrder(numCourses, prerequisites);
        for(int i = 0; i < numCourses; i++){
            System.out.println(order[i]);
        }
    }

}
